package my.leetcode.solution;

/**
 * 思路:
 */
public class P4 {

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1,2}, new int[]{3,4}));
        System.out.println(findMedianSortedArrays(new int[]{}, new int[]{3,4}));
        System.out.println(findMedianSortedArrays(new int[]{}, new int[]{3,4,5}));
        System.out.println(findMedianSortedArrays(new int[]{1,2,3}, new int[]{3,3,4}));
        System.out.println(findMedianSortedArrays(new int[]{3,3,4},new int[]{1,2,3}));
        System.out.println(findMedianSortedArrays(new int[]{1,2}, new int[]{3,4,5}));
    }

    public static double mid(int [] num) {
        int l = num.length, i = l / 2;
        return mid(num, i, (l & 1) == 0);
    }

    public static double mid(int [] num, int p, boolean even) {
        if(even) {
            return 1.0 * (num[p] +  num[p - 1]) / 2;
        } else {
            return num[p];
        }
    }

    public static double mid(int [] min, int [] max) {
        int l = min.length + max.length, p = l / 2;
        if(p < min.length) {
            return mid(min, p, (l & 1) == 0);
        } else if(p == min.length) {
            if((l & 1) == 0) {
                return 1.0 * (min[min.length-1] +  max[0]) / 2;
            } else {
                return min[p];
            }
        } else {
            return mid(max, p - min.length, (l & 1) == 0);
        }
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length, l2 = nums2.length;
        if(l1 == 0) {
            return mid(nums2);
        } else if(l2 == 0) {
            return mid(nums1);
        } else if(nums1[0] >= nums2[l2-1]) {
            return mid(nums2, nums1);
        } else if(nums2[0] >= nums1[l1-1]) {
            return mid(nums1, nums2);
        }

        //p 减1的目的是因为 e1 + e2 + 1 + 1 = (l1 + l2) / 2 + 1
        //limit1 为nums1 不能再退的位置，limit2同理。
        int p = (l1 + l2) / 2 - 1, e1 = 0, e2 = 0, surplus, speedLimit, limit1 = -1, limit2 = -1;
        do {
            if(nums2[e2] > nums1[e1]) {
                //e1这个位置不能再退回去
                limit1 = e1;
                //nums1往前生长
                e1 = Math.min((e1 + l1) / 2, p);
                //剩余个数 - 1（nums2接下来的索引）
                surplus = p - e1;
                //nums2不能往后退了
                if(surplus <= limit2) {
                    //nums2限制生长速度 最多只能退到limit2前一个位置
                    speedLimit = e2 - limit2 - 1;
                    //说明还可以退
                    if(speedLimit > 0) {
                        e1 = limit1 + speedLimit;
                        e2 = p - e1;
                    } else {
                        break;
                    }
                } else {
                    //nums2往后退
                    e2 = surplus;
                }

            } else {

            }
        } while (e1 < l1 && e2 < l2 && (limit1 + limit2) < p);

        return 0;
    }

}
